#include <stdio.h>

int main (int argc, char const* argv[])
{

    int a[1000];
    int i, j, sum, testcase, n, s1, s2;

    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }

        // sort data
        for (i = 0; i < n-1; i++) {
            for (j = i+1; j < n; j++) {
                if (a[i] > a[j]) {
                    int t = a[i];
                    a[i] = a[j];
                    a[j] = t;
                }
            }
        }

        sum = 0;
        while (n > 0) {
            if (1 == n) {
                sum += a[0];
                break;
            }

            if (2 == n) {
                sum += a[1];
                break;
            }

            if (3 == n) {
                sum += a[0] + a[1] + a[2];
                break;
            }

            if (4 <= n) {
                s1 = a[0] + 2 * a[1] + a[n-1];
                s2 = 2 * a[0] + a[n-1-1] + a[n-1];

                if (s1 > s2) {
                    sum += s2;
                } else {
                    sum += s1;
                }
                
                n -= 2;
            }
        }

        printf("%d\n", sum);
    }

    return 0;
}
